package DoExercise.HSP_ZCY.A016_动态规划;

/**
 * 给定数组arr，arr中所有的值都为正数且不重复，每个值代表一种面值的货币，每种面值的货币可以使用任意张
 * 再给定一个整数 aim，代表可以组合的总金额
 * 求组成 aim 的方法数
 * <p>
 * 注意整条的优化轨迹：从暴力递归 -- 记忆搜索 -- 动态规划枚举 -- 最终动态规划
 */
public class Code09_拿货币的方式
{
    public static void main(String[] args)
    {
        int[] arr = {5, 2, 3, 1};
        int sum = 350;
        System.out.println(ways(arr, sum));
        System.out.println(ways2(arr, sum));
        System.out.println(waysDpEnum(arr, sum));
        System.out.println(waysDp(arr, sum));
    }
    
    public static int ways(int[] arr, int aim)
    {
        if (arr == null || arr.length == 0 || aim < 0)
        {
            return 0;
        }
        return process(arr, 0, aim);
    }
    
    
    /**
     * 1 是从下向上不断取值的
     * 2 有效的方式是，当rest=0且每张牌都出现即index = arr.length时有效
     *
     * @param arr
     * @param index
     * @param rest
     * @return
     */
    public static int process(int[] arr, int index, int rest)
    {
        if (index == arr.length) return rest == 0 ? 1 : 0;
        
        int ways = 0;
        //每个面值不断修改张数，不断向后枚举，直到rest被消耗完
        for (int zhang = 0; zhang * arr[index] <= rest; zhang++)
        {
            ways += process(arr, index + 1, rest - zhang * arr[index]);
        }
        return ways;
    }
    
    /**
     * 记忆化搜索方式
     *
     * @param arr
     * @param aim
     * @return
     */
    public static int ways2(int[] arr, int aim)
    {
        if (arr == null || arr.length == 0 || aim < 0)
        {
            return 0;
        }
        int[][] dp = new int[arr.length + 1][aim + 1];
        for (int i = 0; i < dp.length; i++)
        {
            for (int j = 0; j < dp[i].length; j++)
            {
                dp[i][j] = -1;
            }
        }
        return process2(arr, 0, aim, dp);
    }
    
    public static int process2(int[] arr, int index, int rest, int[][] dp)
    {
        if (dp[index][rest] != -1)
        {
            return dp[index][rest];
        }
        
        if (index == arr.length)
        {
            dp[index][rest] = rest == 0 ? 1 : 0;
            return dp[index][rest];
        }
        
        int ways = 0;
        for (int zhang = 0; zhang * arr[index] <= rest; zhang++)
        {
            ways += process2(arr, index + 1, rest - zhang * arr[index], dp);
        }
        dp[index][rest] = ways;
        return ways;
    }
    
    /**
     * 枚举版的动态规划
     *
     * @param arr
     * @param aim
     * @return
     */
    public static int waysDpEnum(int[] arr, int aim)
    {
        if (arr == null || arr.length == 0 || aim < 0) return 0;
        
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 1;
        for (int index = N - 1; index >= 0; index--)
        {
            for (int rest = 0; rest <= aim; rest++)
            {
                int ways = 0;
                for (int zhang = 0; zhang * arr[index] <= rest; zhang++)
                {
                    ways += dp[index + 1][rest - zhang * arr[index]];
                }
                dp[index][rest] = ways;
            }
        }
        return dp[0][aim];
    }
    
    /**
     * 暴力递归
     * 有重复行为，可以优化为动态规划
     *
     * @param arr
     * @param aim
     * @return
     */
    public static int waysDp(int[] arr, int aim)
    {
        if (arr == null || arr.length == 0 || aim < 0) return 0;
        
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 1;//等价于 if (index == arr.length) return rest == 0 ? 1 : 0;
        for (int i = N - 1; i >= 0; i--)//每一行依赖于下面一行
        {
            for (int rest = 0; rest <= aim; rest++)
            {
                dp[i][rest] = dp[i + 1][rest];
                if (rest - arr[i] >= 0)
                {
                    dp[i][rest] += dp[i][rest - arr[i]];//从左向右计算，前面的同行已经计算过的可以直接使用
                }
            }
        }
        return dp[0][aim];
    }
    
}
